package com.scott.ch060;

/**
 * @author 黄后林
 * @version 1.0
 * @note 快速排序
 * @date 2022-03-20 20:10:27
 */
public class Quick {

    //比较元素x是否小于y
    private static boolean less(Comparable x,Comparable y){
        if(x.compareTo(y)<0){
            return true;
        }
        return false;
    }

    //在数组a中交换索引i和索引j处的元素
    private static void exchange(Comparable[] a, int i,int j){
        Comparable tmp = a[i];
        a[i]=a[j];
        a[j]=tmp;
    }


    //对数组进行排序
    public static void  sort(Comparable[] a){

        int low=0;
        int high=a.length-1;
        sort(a,low,high);

    }

    //对数组进行部分排序   low<=index<=high  low=数组中的最小的下标  high=数组中的最大的下标
    public static void  sort(Comparable[] a,int low,int high){

        if( low>=high ){
            //也就是说: 只有当low<high的时候才进行排序
            return ;
        }

        //1 对low<=index<=high的元素进行分组 [ 左子组 和 右子组 ]

        // 第1次返回元素6所在的索引 index=5  [3、1、2、5、4、6、9、7、8]
        int index = partition(a, low, high);

        //2 让左子组有序 [3、1、2]  左边的元素都比分界值6小
        sort(a,low,index-1);

        //3 让右子组有序 [9、7、8]  右边的元素都比分界值6大
        sort(a,index+1,high);

    }

    //对数组进行分组 返回分界值的下标  分界值=参照物
    //low<=index<=high  low=最小的下标  high=最大的下标
    //快速排序的核心算法
    public static int  partition(Comparable[] a,int low,int high){

        //1、确定分界值  第1次的分界值=6
        Comparable key = a[low];

        //2、定义2个指针 [指针 = 下标]  left=待切分元素的最小索引  right=待切分元素的最大索引+1
        int left  = low;
        int right = high+1;

        //3、切分 left从左往右扫描  right从右往左扫描 直到left>=right
        while (true){

            //3.1、移动right指针、从右往左扫描 找到第1个比分界值小的元素 然后停止
            while(less(key,a[--right])){
                //如果分界值比right指针左移1位后指向的值小  也就是说 right指向的值比分界值key大 进入循环

                if(right == low){
                    //说明已经移动到了最左边 结束本次循环
                    break;
                }

            }

            //3.2、移动left指针、 从左往右扫描 找到第1个比分界值大的元素 然后停止
            while(less(a[++left],key)){
                //如果left指针右移1位的值比分界值小 可以进入循环
                if(left == high){
                    //说明已经移动到了最右边 结束本次循环
                    break;
                }
            }

            //3.3、比较left>=right ? '说明元素扫描完毕、结束循环' : '交换位置'
            if(left>=right){

                // 结束整个循环
                //3.4、交换分界值和right指针指向的值  right=left  参考笔记：5.10
                //交换元素3和元素6 返回元素6
                exchange(a,low,right);
                break;
            }else{
                //交换位置
                exchange(a,left,right);
            }
        }

        System.out.println("right="+a[right]);
        return right;
    }
}
